关于微信公众号

首发于安全客

Preface

  现代公钥密码系统中，其实远远不止RSA、DSA、ECC等众所周知的公钥密码系统，最近还学习到了一种比较年轻的公钥密码系统 —— paillier cryptosystem 但是wiki上并没有给出该方案的解密的proof。

Introduce

  Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质 ; 这意味着，仅给出公钥和m1、m2加密，可以计算出m1 + m2

Key generation

The frist pattern：

1. 随机选择两个大质数p、q满足$gcd(pq, (p-1)\cdot (q-1))$。
2. 计算$n=p\cdot q，λ = lcm(p-1, q-1) = \frac{(p-1)\cdot (q-1) }{ gcd(p-1,q-1)}$
3. 选择随机整数g，$0<g<n^2$
4. 定义$L(x) = \frac{(x-1)} { n}$
5. 计算$μ = (L(g^λ \pmod {n^2} ))^{-1} \pmod n$
6. 公钥为$(n，g)$
7. 私钥为$(λ，μ)$

The second pattern（a simpler variant）：

其余参数不变，主要改变了g，λ，μ的定义

1. $g = n+1$
2. $λ = φ(n) = (p-1)\cdot (q-1) $
3. $μ = φ(n)^{-1} \pmod n$

Encryption

1. 设$m$为要加密的消息，显然需要满足，$0 ≤ m ＜ n$
2. 选择随机 $r$，保证$gcd(r, n) = 1$
3. 密文$c$：$c = g^m\cdot r^n \pmod {n^2}$

Decryption

1. $m = ( L( c^λ \pmod {n^2} ) \cdot μ ) \pmod n$

Proof

以下推理过程就用数学公式记录了，如果平台显示不出来的话，建议复制进typora等此类编辑器中食用，下面也会给出截图

The first pattern

由 $L(c^λ \pmod{n^2}\cdot μ) \pmod{n}$

有 $L(g^{mλ}\cdot r^{nλ}\pmod{n^2})\cdot μ \pmod{n}$ ①

其中$λ = \frac{(p-1) \cdot (q-1)}{gcd((p-1)\cdot (q-1))}, μ = L(g^λ \pmod{n^2})^{-1} \pmod{n}$

所以①式=> $L(g^{mλ}\cdot r^{nλ} \pmod{n^2})\cdot L(g^λ \pmod{n^2})^{-1} \pmod{n}$ ②

∵$(p-1)|λ, (q-1)|λ$

∴$λ = k_1(p-1) = k_2(q-1)$

∴$g^λ = g^{k_1(p-1)}\equiv 1 \pmod{p}，即 (g^λ -1) | p$

$ g^λ = g^{k_2(q-1)}\equiv 1 \pmod{q}， 即 (g^λ -1) | q$

∴$ (g^λ -1) | lcm(p,q) ，即 (g^λ -1) | pq，即g^λ \equiv 1 \pmod{n} $

∴$g^λ \pmod{n^2} \equiv 1\pmod{n}$

∴$g^λ\pmod{n^2} = k_gn+1; k<n$

∴$L(g^λ\pmod{n^2}) = k_g$

且有

1. $1+kn \equiv 1+kn \pmod{m^2}$

2. $(1+kn)^2 \equiv 1+2kn+(kn)^2 \equiv 1+2kn \pmod{m^2}$

3. $(1+kn)^3 \equiv 1+3(kn)^2+3kn+(kn)^3 \equiv 1+3kn \pmod{m^2}$

   这里我们就不用数学分析法了，就直接易得了

   => $(1+kn)^{m} \equiv knm+1 \pmod{n^2}$

∴$g^{mλ} = (1+k_gn)^{m} \equiv k_gnm+1 \pmod{n^2}$

∴$r^{nλ} = (1+k_nn)^{n} \equiv k_nn^2+1 \equiv 1\pmod{n^2}$

∴$L(g^{mλ}\cdot r^{nλ}\pmod{n^2}) = L(k_gnm+1)=mk_g$

又∴$L(g^λ\pmod{n^2}) = k_g$

∴②式： $L(g^{mλ} \cdot r^{nλ} \pmod{n^2})\cdot L(g^λ \pmod{n^2})^{-1} \pmod{n}$ => $mk_g\cdot k_g^{-1} \equiv m \pmod n$

证毕

The second pattern

由 $L(c^λ \pmod{n^2} \cdot μ) \pmod{n}$

有 $L(g^{mλ}\cdot r^{nλ} \pmod{n^2} \cdot μ) \pmod{n}$ ①

其中$λ = (p-1)*(q-1)， μ = φ(n)^{-1} \pmod{n}$

∵$r^{nλ} = r^{n(p-1) \cdot (q-1)} = r^{φ(n^2)}$

由欧拉定理：$r^{φ(n^2)} \equiv 1 \pmod{n^2}$

①式 => $L(g^{mλ} \pmod{n^2} \cdot μ) \pmod{n}$ ②

∵$g = n+1$

∴$g^{mλ} = (1+n)^{mλ} \equiv nmλ+1 \pmod{n^2}$

②式=> $L((nmλ+1) \cdot μ) \pmod{n}$

=> $ \frac{(nmλ+1)-1}{n} \cdot μ \pmod{n}$

=>$(mλ \cdot μ) \pmod{n}$ ③

∵$λ = φ(n)，μ = φ(n)^{-1} \pmod{n}$

∴③式： $(mλ \cdot μ) \equiv m\pmod{n}$

证毕

DASCTF四月月赛 not RSA

from Crypto.Util.number import getPrime as bytes_to_long
from secret import flag,p,q
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)

print "c=%d"%(c)
print "n=%d"%(n)

可以看到，这一题就是用的paillier cryptosystem，且参数用的是上文中的The second pattern

但是我们计算$λ = φ(n) = (p-1)\cdot (q-1)$ ，需要用到p和q

这里我们直接上yafu分解n发现可以成功分解，原因是p与q其实非常接近，所以其实直接对n开根然后再在附近寻找素数就能找到p、q了。

所以构造解密脚本

# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes,inverse
from sympy import nextprime
from gmpy2 import iroot

def L(x,n):
    return (x-1)/n


c=
n=

#factor(n)
a = iroot(n,2)[0]
p = nextprime(a)
q = n//p
assert p*q == n

#根据解密公式，计算所需私钥对（λ，μ）
Lambda=(p-1)*(q-1)
miu=inverse(Lambda,n*n)
m=(L(pow(c,Lambda,n**2),n)*miu)%n

print long_to_bytes(m)

Homomorphic properties

Homomorphic addition of plaintexts

设D为解密函数，E为加密函数

即：$D(E(m_1, r_1)\cdot E(m_2,r_2) \pmod {n^2})≡ m_1+m_2 \pmod n$

proof

$C = (g^{m_1}) \cdot (r_1^n) \cdot (g^{m_2}) \cdot (r_2^n) \pmod {n^2} $

 $= g^{m_1+m_2}\cdot (r_1\cdot r_2)^n \pmod {n^2}$

首先我们可以将$m_1+m_2$看作一个整体$M$，然后由于$r_1、r_2$是随机选的，所以$r_1\cdot r_2$可以看作一个整体$R$

故$C = g^M \cdot R^n \pmod {n^2}$

由于$gcd(r_1,n) = 1; gcd(r_2,n) = 1； => gcd(r_1\cdot r_2, n) = 1$，故$R$符合要求

所以$D(C) = M ≡ m_1 + m_2 \pmod n$

Homomorphic multiplication of plaintexts

设D为解密函数，E为加密函数

即：$D(E(m_1, r_1)^k \pmod {n^2})≡ km_1 \pmod n$

proof

$C = (g^{m_1}) \cdot (r_1^n)^k\pmod {n^2} $

 $=(g^{km_1}\cdot (r_1^{kn} )\pmod {n^2}$

首先我们可以将$km_1$看作一个整体$M$，然后由于$r_1$是随机选的，所以$r_1^k$可以看作一个整体R，

故$C = g^M \cdot R^n \pmod {n^2}$

由于$gcd(r_1,n) = 1 => gcd(r_1^k, n) = 1$，故$R$符合要求

所以$D(C) = M ≡ km_1 \pmod n$

Reference

https://en.wikipedia.org/wiki/Paillier_cryptosystem

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com